package com.lc.hot100.lc41;

import java.util.*;

public class Main {

}

class Solution1 {
    public int firstMissingPositive(int[] nums) {
        
    	int n = nums.length;
    	Set<Integer> set = new HashSet<>();
    	for (int i = 0; i < n; i ++) {
    		if (nums[i] > 0) {
    			set.add(nums[i]);
    		}
    	}
    	
    	for (int i = 1; i <= n; i ++) {
    		if (!set.contains(i)) {
    			return i;
    		}
    	}
    	return 0;
    	
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        
    	int n = nums.length;
    	
    	for (int i = 0; i < n; i ++) {
    		if (nums[i] <= 0) {
    			nums[i] = n + 1;
    		}
    	}
    	
    	for (int i = 0; i < n; i ++) {
    		int t = Math.abs(nums[i]);
    		if (t < n + 1) {
    			nums[t - 1] = -Math.abs(nums[t - 1]);
    		}
    	}
    	
    	for (int i = 0; i < n; i ++) {
    		if (nums[i] > 0) {
    			return i + 1;
    		}
    	}
    	
    	return n + 1;
    	
    }
}
